Quantum Factorization Algorithm: QFT and Shor Algorithm

Let’s express \(k\) as binary \(k:=k_{1}k_{2}\dots k_{D}\). Then, \(\ket{\phi_{k}}\) can be expressed by tensor products, i.e., it’s a product state.

\[ \ket{\phi_{k}} = \otimes_{l=1}^{n} \frac{\ket{0} + e^{2\pi i \ 0.j_{n-l+1}j_{n-l+2}\dots j_{n}}\ket{1}}{\sqrt{2}} \]

The \(0.j_{i}\dots j_{n}\) is an abbreviation of \(\frac{j_{i}}{2^{1}} + \dots + \frac{j_{n}}{2^{n-i+1}}\)

For an \(n\)-qubit quantum system \(\ket{j} = \ket{j_{1}j_{2}\cdots j_{n}}\), expanding Fourier basis \(\ket{e_{j}}\)¹ gives

\[ |e_j\rangle = \left( \frac{|0\rangle + e^{2\pi i (0.j_n)}|1\rangle}{\sqrt{2}} \right) \otimes \left( \frac{|0\rangle + e^{2\pi i (0.j_{n-1}j_n)}|1\rangle}{\sqrt{2}} \right) \otimes \cdots \otimes \left( \frac{|0\rangle + e^{2\pi i (0.j_1 j_2 \dots j_n)}|1\rangle}{\sqrt{2}} \right) \]

Ordering Problem.

As a result, to avoid ordering problem, we can apply quantum gates in a reverse order.

1. First apply Hadamard gate \(H\) to \(\ket{j_{1}}\). Then, apply gate \(\frac{|0\rangle + e^{2\pi i (0.j_1 j_2 \dots j_n)}|1\rangle}{\sqrt{2}}\) conditioned by \(j_{2}\cdots j_{n}\), here, \(j_{2}\cdots j_{n}\) are still unmodified and are either \(\ket{0}\) or \(\ket{1}\). But to note that, this should be the output state of \(\ket{j_{n}}\)
2. Repeat step 1. Finally, we apply \(H\), then \(\frac{|0\rangle + e^{2\pi i (0.j_n)}|1\rangle}{\sqrt{2}}\) to \(\ket{j_{n}}\) conditioned on \(\ket{j_{n}}\). But this should be the output state of \(\ket{j_{1}}\).

After applied all gates, we use \(\frac{n}{2}\) SWAP gates to obtain the correct ordering.

We apply controlled-gate \(C(U)\) to control bit \(\ket{+}\) and target bit \(\ket{u}\), we get

\[\begin{aligned} & C(U) \left( \frac{\ket{0}+\ket{1}}{\sqrt{2}} \otimes \ket{u} \right) \\ = & \frac{\ket{0}\ket{u} + \ket{1} (U\ket{u})}{\sqrt{2}} \\ = & \left( \frac{\ket{0} + e^{2\pi i \varphi}\ket{1}}{\sqrt{2}} \right) \otimes \ket{u} \end{aligned}\]

So we can see that the global phase \(e^{2\pi i\varphi}\) has been moved to the control bit.

The input consists of (1) controlled-gate \(C(U)\) as an oracle; (2) an eigenstate \(\ket{u}\) of \(C(U)\) with eigenvalue \(e^{2\pi i \varphi}\). It follows the following procedure.

1. Prepare 2 registers: master register (stores \(t\) \(\ket{0}^{\otimes t}\)-initialized qubits), input register that stores \(\ket{u}\). The overall system’s composite quantum state is \[ \ket{\psi_{0}} = \ket{0}^{\otimes t} \otimes \ket{u} \]
2. Apply Hadamard gate to all qubits on master register, to generate equa-weight superposition state. \[ \ket{\psi_{1}} = (H^{\otimes t} \ket{0}^{\otimes t}) = \frac{1}{\sqrt{2^{t}}} \sum_{j=0}^{2^{t}-1} \ket{j}\otimes \ket{u} \]

3. For \(k=1,2,\cdots,t\), apply \(2^{t-k}\) controlled-gate \(C(U)\) with \(k\)-th qubit on the master register being control bit and the input register being target bit. Or equivalently, apply \(C(U^{2^{t-k}})\) controlled-gate.

   So here, according to \(U\ket{u}=e^{2\pi i \varphi}\ket{u}\), when the control qubit is \(\ket{1}\), the phase is “kicked-back” to the qubit on master register and the input register remains unchanged.

   After all controlled-gates are applied, equivalently, we applied \(U^{j}\) transformation to each computation basis \(\ket{j}\). So the system becomes superposition state under Fourier basis: \[ |\psi_2\rangle = \frac{1}{\sqrt{2^t}} \sum_{j=0}^{2^t-1} e^{2\pi i \varphi j} |j\rangle \otimes |u\rangle \]

4. Apply inverse QFT (\(FT^{\dagger}\)) to master register, and measure in the computational basis of \(t\) qubits.
5. Output \(\hat{\varphi}=0.j_{1}j_{2}\cdots j_{t}\)

So next, we need to construct \(C(O)\) and \(\ket{u_{s}}\) for some \(s\).

Instead of construct \(O \to C(O) \to O_{QPE}\), we directly construct the QPE oracle over \(t\) qubits for the modular multiplication oracle \(O\). We conclude that

\[ O_{QPE} = \sum_{j=0}^{2^{t}-1} \ket{j}\bra{j} \otimes O^{j} \]

is equal to \(O_{x,N}\), i.e., \(O_{QPE}=O_{x,N}\), where \(O_{x,N}\) is the oracle for \(f(a)=x^{a} \pmod N\). It acts on the system \(\ket{x}\) and ancilla \(\ket{q}\) of length \((\log N)\)-bits.

\[ O_{x,N}:\ket{a}\ket{q}\mapsto\ket{a}\ket{q\cdot x^{a}\pmod N} \]

\(O_{x,N}\) on \(t\)-qubits can be realized with \(O(t^{3})=O(\log^{3} N)\) gates.

We cannot directly construct \(\ket{u_{s}}\) since we don’t know \(r\).